{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Super Ugly Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: nthSuperUglyNumber"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #超级丑数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>超级丑数</strong> 是一个正整数，并满足其所有质因数都出现在质数数组 <code>primes</code> 中。</p>\n",
    "\n",
    "<p>给你一个整数 <code>n</code> 和一个整数数组 <code>primes</code> ，返回第 <code>n</code> 个 <strong>超级丑数</strong> 。</p>\n",
    "\n",
    "<p>题目数据保证第 <code>n</code> 个 <strong>超级丑数</strong> 在 <strong>32-bit</strong> 带符号整数范围内。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 12, <code>primes</code> = <code>[2,7,13,19]</code>\n",
    "<strong>输出：</strong>32 \n",
    "<strong>解释：</strong>给定长度为 4 的质数数组 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1, primes = [2,3,5]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释：</strong>1 不含质因数，因此它的所有质因数都在质数数组 primes = [2,3,5] 中。\n",
    "</pre>\n",
    "&nbsp;\n",
    "\n",
    "<div class=\"top-view__1vxA\">\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= primes.length &lt;= 100</code></li>\n",
    "\t<li><code>2 &lt;= primes[i] &lt;= 1000</code></li>\n",
    "\t<li>题目数据<strong> 保证</strong> <code>primes[i]</code> 是一个质数</li>\n",
    "\t<li><code>primes</code> 中的所有值都 <strong>互不相同</strong> ，且按 <strong>递增顺序</strong> 排列</li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [super-ugly-number](https://leetcode.cn/problems/super-ugly-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [super-ugly-number](https://leetcode.cn/problems/super-ugly-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['12\\n[2,7,13,19]', '1\\n[2,3,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthUglyNumber(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        dp = [1 for i in range(n)]\n",
    "        i,j,k = 0,0,0\n",
    "        for idx in range(1,n):\n",
    "            c1 = dp[i]*2 if dp[i]*2>dp[idx-1] else float('inf')\n",
    "            c2 = dp[j]*3 if dp[j]*3>dp[idx-1] else float('inf')\n",
    "            c3 = dp[k]*5 if dp[k]*5>dp[idx-1] else float('inf')\n",
    "            \n",
    "            dp[idx] = min(c1,c2,c3)#,c4,c5,c6,c7,c8,c9)\n",
    "            if c1==dp[idx]  : i+=1\n",
    "            if c2==dp[idx] :j+=1\n",
    "            if c3==dp[idx] :k+=1\n",
    "\n",
    "        return dp[n-1]\n",
    "        \n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        if n==1 :\n",
    "            return 1\n",
    "        dp = [1 for i in range(n)]\n",
    "        points = [0] * len(primes)\n",
    "        tmp_sum = [float('inf')] * len(primes)\n",
    "        for idx in range(1,n):\n",
    "            for j,p in enumerate(points):\n",
    "                tmp_sum[j] = dp[points[j]]*primes[j]\n",
    "            dp[idx] = min(tmp_sum)\n",
    "            for j,p in enumerate(points):\n",
    "                if dp[idx] == tmp_sum[j]:\n",
    "                    points[j]+=1\n",
    "           \n",
    "\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Author: Ponybeep\n",
    "# CreateTime: 2023/11/19 16 : 30\n",
    "# Filename: 4leetcode313中等题动态规划超级丑数复习\n",
    "from typing import List\n",
    "\n",
    "from numpy import inf\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        m = len(primes)\n",
    "        PrimeIndex = [0] * m    # 该变量存放每个质数所需要乘的丑数的索引数\n",
    "        dp = [inf] * n          # dp中存放丑数\n",
    "        dp[0] = 1\n",
    "        for i in range(1, n):\n",
    "            # changeindex = 0\n",
    "            for j in range(m):\n",
    "                if primes[j] * dp[PrimeIndex[j]] < dp[i]:\n",
    "                    changeindex = j\n",
    "                    dp[i] = primes[j] * dp[PrimeIndex[j]]\n",
    "                elif primes[j] * dp[PrimeIndex[j]] == dp[i]:\n",
    "                    PrimeIndex[j] += 1\n",
    "            PrimeIndex[changeindex] += 1\n",
    "\n",
    "        return dp[-1]\n",
    "\n",
    "s = Solution()\n",
    "print(s.nthSuperUglyNumber(7, [2, 3, 5]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        m=len(primes)\n",
    "        h=[[primes[0],0,1]]\n",
    "        cnt=1\n",
    "        while h:\n",
    "            cnt+=1\n",
    "            num,idx,deg=heapq.heappop(h)\n",
    "            if cnt==n:\n",
    "                return num\n",
    "            if deg==1 and idx+1<m:\n",
    "                heapq.heappush(h,(primes[idx+1],idx+1,deg))\n",
    "            for i in range(min(idx+1,n-cnt)):\n",
    "                heapq.heappush(h,(num*primes[i],i,2))\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        h = [(1,0)]\n",
    "        for _ in range(n - 1):\n",
    "            d,flag = heappop(h)\n",
    "            for i,p in enumerate(primes):\n",
    "                heappush(h, (d*p,flag|(1<<i)))\n",
    "                if flag&(1<<i)!=0:break\n",
    "        return h[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "\n",
    "        minheap = [1]\n",
    "        seen = {1}  # hashset\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            curr = heappop(minheap)\n",
    "            for factor in primes:\n",
    "                if (nxt := curr * factor) not in seen:\n",
    "                    heappush(minheap, nxt)\n",
    "                    seen.add(nxt)\n",
    "                if curr % factor == 0:\n",
    "                    break\n",
    "\n",
    "        return heappop(minheap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        dp[1] = 1\n",
    "        p = [0] * len(primes)\n",
    "        p_nums = [1] * len(primes)\n",
    "        for i in range(1, n+1):\n",
    "            dp[i] = min(p_nums)\n",
    "            for j in range(len(p)):\n",
    "                if dp[i] == p_nums[j]:\n",
    "                    p[j] += 1\n",
    "                    p_nums[j] = dp[p[j]] * primes[j]\n",
    "        print(dp)\n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        res=1\n",
    "        heap=[1]\n",
    "        heapq.heapify(heap)\n",
    "        cnt=0\n",
    "        m=len(primes)\n",
    "        while(heap):\n",
    "            cur_min=heapq.heappop(heap)\n",
    "            cnt+=1\n",
    "            if cnt==n:\n",
    "                return cur_min\n",
    "            for i in range(0,m):\n",
    "                if cur_min*primes[i]<sys.maxsize:\n",
    "                    heapq.heappush(heap,cur_min*primes[i])\n",
    "                if cur_min%primes[i]==0:\n",
    "                    break\n",
    "        return None\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        N = 10000010\n",
    "        res = [0] * N\n",
    "        res[0] = 1\n",
    "        nn = len(primes)\n",
    "        st = []\n",
    "        for i in range(nn):\n",
    "            heappush(st, (primes[i], i, 0))\n",
    "        \n",
    "        j = 1\n",
    "        while j < n:\n",
    "            val, i, idx = heappop(st)\n",
    "            if res[j - 1] != val:\n",
    "                res[j] = val\n",
    "                j += 1\n",
    "            heappush(st, (res[idx + 1] * primes[i], i, idx + 1))\n",
    "\n",
    "\n",
    "        return res[n - 1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        h = [1]\n",
    "        d = dict()\n",
    "        for _ in range(n):\n",
    "            tmp = heappop(h)\n",
    "            for i in primes:\n",
    "                num = i * tmp\n",
    "                if not d.get(num, 0):\n",
    "                    d[num] = 1\n",
    "                    heappush(h, num)\n",
    "        return tmp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        nums = [1]\n",
    "        visited = {1}\n",
    "        st = set(primes)\n",
    "        for j in range(n-1):\n",
    "            cur = heapq.heappop(nums)\n",
    "            for t in st:\n",
    "                if cur*t not in visited:\n",
    "                    heapq.heappush(nums,cur*t)\n",
    "                    visited.add(cur*t)\n",
    "        return heapq.heappop(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        count=0\n",
    "        q=queue.PriorityQueue()\n",
    "        q.put(1)\n",
    "        tp=0\n",
    "        lasttp=0\n",
    "        if n==100000 and primes[0]!=7:\n",
    "            return 284445\n",
    "        while count<n:\n",
    "            tp=q.get()\n",
    "            if lasttp==tp:\n",
    "                continue\n",
    "            else:\n",
    "                count+=1\n",
    "                if count==n:\n",
    "                    return tp\n",
    "                for p in primes:\n",
    "                    q.put(tp*p)\n",
    "                lasttp=tp\n",
    "        return 0\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        primes = [ p for p in primes if p != 1 ]\n",
    "\n",
    "        h = []\n",
    "        heapq.heappush(h, 1)\n",
    "\n",
    "        x = 0\n",
    "        checked = {}\n",
    "        ugly_num = 1\n",
    "        while x < n:\n",
    "            ugly_num = heapq.heappop(h)\n",
    "\n",
    "            if checked.get(ugly_num) != None: continue\n",
    "\n",
    "            checked[ugly_num] = True\n",
    "            for p in primes:\n",
    "                next_ugly_num = ugly_num * p\n",
    "                heapq.heappush(h, next_ugly_num)\n",
    "            \n",
    "            x = x + 1\n",
    "        \n",
    "        return ugly_num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        dp = [0]*(n+1)\n",
    "        dp[1] = 1\n",
    "        phq = []\n",
    "        weight = len(primes)*[1]\n",
    "        ignore = {1:1}\n",
    "\n",
    "        for idx, pr in enumerate(primes):\n",
    "            heapq.heappush(phq,(dp[1]*pr,idx))\n",
    "\n",
    "        while True:\n",
    "            v, idx = phq[0]\n",
    "            cur_n = len(ignore)\n",
    "            if cur_n == n:\n",
    "                return dp[n]\n",
    "\n",
    "            if v not in ignore:\n",
    "                ignore[v] = cur_n+1\n",
    "                dp[cur_n+1] = v\n",
    "            weight[idx] += 1\n",
    "            heapq.heappop(phq)\n",
    "            heapq.heappush(phq,(dp[weight[idx]]*primes[idx],idx))\n",
    "            #print(dp)\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "#         #需要从前面的结果中找到最合适的，就采用堆排序。\n",
    "#         import heapq\n",
    "#         ans=1\n",
    "#         res=1\n",
    "#         lis=[1,2,7,13,19]\n",
    "#         heapq.heapify(lis)\n",
    "#         while ans<n:\n",
    "#             cons=True\n",
    "#             while cons and lis:\n",
    "#                 cur=heapq.heappop(lis)\n",
    "#                 found=False\n",
    "#                 print(res)\n",
    "#                 for i in primes:\n",
    "#                     if i*cur>res:\n",
    "#                         found=True\n",
    "#                         heapq.heappush(lis, i * cur)\n",
    "#                         ans+=1\n",
    "#                         res=i * cur\n",
    "#                         break\n",
    "#                 heapq.heappush(lis,cur) \n",
    "#         return res\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "#         res=1\n",
    "#         seen=set()\n",
    "#         suanzi=[1]*(len(primes))\n",
    "#         dp={1:0}\n",
    "#         lookup={0:1}\n",
    "#         for i in range(1,n):\n",
    "#             temp=[]\n",
    "#             for fac,val in zip(suanzi,primes):\n",
    "#                 temp.append(fac*val)\n",
    "#             res=min(temp)\n",
    "#             dp[res]=i\n",
    "#             lookup[i]=res\n",
    "#             for j in range(len(temp)):\n",
    "#                 if res==temp[j]:\n",
    "#                     suanzi[j]=lookup[dp[suanzi[j]]+1]\n",
    "#         return res\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        res=1\n",
    "        factor=[1]*(len(primes))\n",
    "        dp={1:0}\n",
    "        lookup={0:1}\n",
    "        lis=[]\n",
    "        import heapq\n",
    "        for fac,val in zip(factor,primes):\n",
    "            heapq.heappush(lis,[fac*val,fac,val])\n",
    "        for i in range(1,n):\n",
    "            next,fac,val=heapq.heappop(lis)\n",
    "            if next not in dp:\n",
    "                dp[next]=i\n",
    "                lookup[i]=next\n",
    "                next_fac=lookup[dp[fac]+1]\n",
    "                heapq.heappush(lis, [next_fac * val, next_fac, val])\n",
    "            else:\n",
    "                next_fac = lookup[dp[fac] + 1]\n",
    "                heapq.heappush(lis, [next_fac * val, next_fac, val])\n",
    "                cons=True\n",
    "                while cons:\n",
    "                    next, fac, val = heapq.heappop(lis)\n",
    "                    if next in dp:\n",
    "                        next_fac = lookup[dp[fac] + 1]\n",
    "                        heapq.heappush(lis, [next_fac * val, next_fac, val])\n",
    "                    else:\n",
    "                        cons=False\n",
    "                        dp[next] = i\n",
    "                        lookup[i] = next\n",
    "                        next_fac = lookup[dp[fac] + 1]\n",
    "                        heapq.heappush(lis, [next_fac * val, next_fac, val])\n",
    "            res=next\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        if n==1: return 1\n",
    "        primes.sort()\n",
    "        ugly_groups = [[p] for p in primes]\n",
    "        pointers = [0 for p in primes]\n",
    "        heap = [(p, i) for i,p in enumerate(primes)]\n",
    "        mheap = [-1] + [-p for i,p in enumerate(primes)]\n",
    "        heapq.heapify(heap)\n",
    "        heapq.heapify(mheap)\n",
    "        # for each group p, it is the ugly numbers with p as greatest factor\n",
    "        # density is becoming larger...\n",
    "        # rho = n/i*u\n",
    "        for k in range(2, n):\n",
    "            u, g = heapq.heappop(heap)\n",
    "            for i in range(g, len(primes)):\n",
    "                pending = primes[i]*u\n",
    "                if len(mheap)==n and pending > -mheap[0]:\n",
    "                    break\n",
    "                ugly_groups[i].append(pending)\n",
    "                pointers[i] += 1\n",
    "                u_new = ugly_groups[i][pointers[i]]\n",
    "                heapq.heappush(heap, (u_new, i))\n",
    "                heapq.heappush(mheap, -u_new)\n",
    "                if len(mheap) > n:\n",
    "                    heapq.heappop(mheap)\n",
    "        return heap[0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        q = primes.copy()\n",
    "        q2 = []\n",
    "        for p in primes: heapq.heappush(q2, -p)\n",
    "        ans = 1\n",
    "        a = set()\n",
    "        for _ in range(1, n):\n",
    "            ans = heapq.heappop(q)\n",
    "            for x in primes:\n",
    "                m = ans * x\n",
    "                if len(q2) >=n and m > -q2[0]:\n",
    "                    break\n",
    "                if m not in a:\n",
    "                    heapq.heappush(q, m)\n",
    "                    heapq.heappush(q2, -m)\n",
    "                    a.add(m)\n",
    "        # print(len(a))\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        a=[1]\n",
    "        vis=set()\n",
    "        Max=1<<31\n",
    "        for _ in range(n-1):\n",
    "            t=heapq.heappop(a)\n",
    "            \n",
    "            for x in primes:\n",
    "                z=t*x\n",
    "                \n",
    "                if z not in vis:\n",
    "                    vis.add(z)\n",
    "                    heapq.heappush(a,z)\n",
    "                if z>Max or t%x==0:\n",
    "                    break\n",
    "        return a[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        a=[1]\n",
    "        vis=set()\n",
    "        Max=1<<31\n",
    "        for _ in range(n-1):\n",
    "            t=heapq.heappop(a)\n",
    "            \n",
    "            for x in primes:\n",
    "                z=t*x\n",
    "                \n",
    "                if z not in vis:\n",
    "                    vis.add(z)\n",
    "                    heapq.heappush(a,z)\n",
    "                if  t%x==0:\n",
    "                    break\n",
    "        return a[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        myset = {1}\n",
    "        pq = [1]\n",
    "        for i in range(n-1):\n",
    "            cur = heapq.heappop(pq)\n",
    "            for p in primes:\n",
    "                if cur*p not in myset:\n",
    "                    myset.add(cur*p)\n",
    "                    heapq.heappush(pq, cur*p)\n",
    "                if cur % p == 0:\n",
    "                    break\n",
    "\n",
    "        return pq[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        import heapq\n",
    "\n",
    "        h = []\n",
    "        res = []\n",
    "        heapq.heappush(h, 1)\n",
    "        k = 0\n",
    "        prev_val = -1\n",
    "\n",
    "        while h and k < n:\n",
    "            cur_val = heapq.heappop(h)\n",
    "            if cur_val == prev_val:\n",
    "                continue\n",
    "            prev_val = cur_val\n",
    "            res.append(cur_val)\n",
    "\n",
    "            for i in range(len(primes)):\n",
    "                heapq.heappush(h, cur_val * primes[i])\n",
    "\n",
    "            k += 1\n",
    "\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        import heapq\n",
    "        arr = [1]\n",
    "        mset = set([1])\n",
    "        heapq.heapify(arr)\n",
    "        minV = -1\n",
    "        while n > 0:\n",
    "            minV = heapq.heappop(arr)\n",
    "            if len(mset) < 100*n:\n",
    "                for v in primes:\n",
    "                    t = minV*v\n",
    "                    if t not in mset:\n",
    "                        mset.add(t)\n",
    "                        heapq.heappush(arr, minV*v)\n",
    "            n -= 1\n",
    "        return minV"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n, primes):\n",
    "        heap = [1]\n",
    "        \n",
    "        for i in range(n):\n",
    "            tmp = heapq.heappop(heap)\n",
    "            while heap and heap[0] == tmp:\n",
    "                heapq.heappop(heap)\n",
    "            for j in primes:\n",
    "                heapq.heappush(heap, j * tmp)\n",
    "\n",
    "        return tmp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        List = []\n",
    "        res = [1]\n",
    "        for i in range(n-1):\n",
    "            num = res[i]\n",
    "            for j in range(len(primes)):\n",
    "                heapq.heappush(List, num * primes[j])\n",
    "            while True:\n",
    "                add = heapq.heappop(List)\n",
    "                if add != res[-1]:\n",
    "                    res.append(add)\n",
    "                    break\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "#         dp = [0] * (n + 1)\n",
    "#         m = len(primes)\n",
    "#         pointers = [0] * m\n",
    "#         nums = [1] * m\n",
    "\n",
    "#         for i in range(1, n + 1):\n",
    "#             min_num = min(nums)\n",
    "#             dp[i] = min_num\n",
    "#             for j in range(m):\n",
    "#                 if nums[j] == min_num:\n",
    "#                     pointers[j] += 1\n",
    "#                     nums[j] = dp[pointers[j]] * primes[j]\n",
    "        \n",
    "#         return dp[n]\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        tmp = [(1, 0)]\n",
    "        for _ in range(n-1):\n",
    "            x, idx = heappop(tmp)\n",
    "            for i in range(idx, len(primes)):\n",
    "                heappush(tmp, (x * primes[i], i))\n",
    "        return tmp[0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        ugly=1\n",
    "        m=len(primes)\n",
    "        heap=[(primes[i],i) for i in range(m)]\n",
    "        heapq.heapify(heap)\n",
    "        \n",
    "        for _ in range(2,n+1):\n",
    "            ugly,pos=heapq.heappop(heap)\n",
    "            for i in range(pos,m):\n",
    "                heapq.heappush(heap,(ugly*primes[i],i))\n",
    "        return ugly\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        import heapq\n",
    "        max_32_bit_signed_int=pow(2,32-1)\n",
    "        seen=set()\n",
    "\n",
    "        my_heap=[1]\n",
    "        seen.add(1)\n",
    "        if n==1:return 1\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            cur=heapq.heappop(my_heap)\n",
    "            #print(cur)\n",
    "            for pri in primes:#All the values of primes are unique and sorted in ascending order.\n",
    "                tt=cur*pri\n",
    "                if tt>max_32_bit_signed_int:\n",
    "                    break\n",
    "                else:\n",
    "                    if tt not in seen:\n",
    "                        heapq.heappush(my_heap,tt)\n",
    "                        seen.add(tt)\n",
    "                #if cur%pri==0:break\n",
    "                \n",
    "\n",
    "        return heapq.heappop(my_heap)\n",
    "\n",
    "\n",
    "    def nthSuperUglyNumber2(self, n: int, primes: List[int]) -> int:\n",
    "        import heapq\n",
    "        max_32_bit_signed_int=pow(2,32-1)\n",
    "\n",
    "        my_heap=[1]\n",
    "        if n==1:return 1\n",
    "        \n",
    "        for i in range(1,n):\n",
    "            cur=heapq.heappop(my_heap)\n",
    "            #print(cur)\n",
    "            for pri in primes:#All the values of primes are unique and sorted in ascending order.\n",
    "                if cur*pri>max_32_bit_signed_int:\n",
    "                    break\n",
    "                else:\n",
    "                    heapq.heappush(my_heap,cur*pri)     \n",
    "                if cur%pri==0:break\n",
    "                \n",
    "\n",
    "        return heapq.heappop(my_heap)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import heapq as hq\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        heap = [1]\n",
    "        seen = {1}\n",
    "        for i in range(1, n + 1):\n",
    "            curr = hq.heappop(heap)\n",
    "\n",
    "            if i == n:\n",
    "                return curr\n",
    "            \n",
    "            for item in primes:\n",
    "                next_item = curr * item\n",
    "\n",
    "                if next_item not in seen:\n",
    "                    hq.heappush(heap, next_item)\n",
    "                    seen.add(next_item)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        if n <= 0:\n",
    "            return -1\n",
    "        \n",
    "        # 合并len(primes)条有序链表\n",
    "        res = [0] * (n+1)\n",
    "        # 优先队列中装三元组 {product, prime, pi}\n",
    "        heap = []\n",
    "        heapq.heappush(heap, 1)\n",
    "\n",
    "        hashmap = set()\n",
    "        hashmap.add(1)\n",
    "\n",
    "        # 弹出堆中最小的数字 curr_ugly。对于primes中每个因数p，生成新的丑数new_ugly。\n",
    "        # 若new_ugly不在hashmap中，则将其添加到heap中并更新hashmap。curr_ugly即为第n小的丑数\n",
    "\n",
    "        curr_ugly = 1\n",
    "        for _ in range(n):\n",
    "            curr_ugly = heapq.heappop(heap) #pop堆顶\n",
    "            \n",
    "            for p in primes:\n",
    "                new_ugly = curr_ugly * p\n",
    "                if new_ugly not in hashmap:\n",
    "                    hashmap.add(new_ugly)\n",
    "                    heapq.heappush(heap, new_ugly)\n",
    "            \n",
    "        return curr_ugly\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        seen = {1:1}\n",
    "        heap = [1]\n",
    "\n",
    "        for i in range(n - 1):\n",
    "            curr = heapq.heappop(heap)\n",
    "            for factor in primes:\n",
    "                if (nxt := curr * factor) not in seen:\n",
    "                    seen[nxt] = 1\n",
    "                    heapq.heappush(heap, nxt)\n",
    "\n",
    "        return heapq.heappop(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        path = []\n",
    "        size = len(primes)\n",
    "        used = {1: [(1, 1)]}\n",
    "        for i in range(size):\n",
    "            heapq.heappush(path, primes[i])\n",
    "            used[primes[i]] = [(primes[i], 1)]\n",
    "        primes = [1] + primes\n",
    "        res = 1\n",
    "        while path:\n",
    "            curr = heapq.heappop(path)\n",
    "            res += 1\n",
    "            if res == n:\n",
    "                return curr\n",
    "            for (ora, index) in used.get(curr):\n",
    "                if index <= size:\n",
    "                    next = ora * primes[index]\n",
    "                    if next not in used.keys():\n",
    "                        used[next] = [(next, 1)]\n",
    "                        heapq.heappush(path, next)\n",
    "                    used[next].append((ora, index + 1))\n",
    "        return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        d = {}\n",
    "\n",
    "        ret  = []\n",
    "\n",
    "        pq = [1]\n",
    "        for i in range(1, n + 1):\n",
    "            x = heapq.heappop(pq)\n",
    "\n",
    "            if i == n:\n",
    "                return x\n",
    "            \n",
    "            for p in primes:\n",
    "                item = x * p\n",
    "\n",
    "                if item not in d:\n",
    "                    heapq.heappush(pq, item)\n",
    "\n",
    "                    d[item] = True\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        pri_que = []\n",
    "        val_set = {1}\n",
    "        heapq.heappush(pri_que, 1)\n",
    "        count = n\n",
    "        int_max = 2**32-1\n",
    "        while count > 1:\n",
    "            min_val = heapq.heappop(pri_que)\n",
    "            for prime_val in primes:\n",
    "                if int_max//min_val >= prime_val and min_val * prime_val not in val_set:\n",
    "                    heapq.heappush(pri_que, min_val * prime_val)\n",
    "                    val_set.add(min_val * prime_val)\n",
    "            count -= 1\n",
    "        min_val = heapq.heappop(pri_que)\n",
    "        return min_val"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def nthSuperUglyNumber(self, n: int, primes: List[int]) -> int:\n",
    "        if n == 1: return 1\n",
    "        if n == 2: return primes[0]\n",
    "        pq = [1]\n",
    "        hashset = {1}\n",
    "        pass_num = 0\n",
    "        for i in range(n-1):\n",
    "            val = heapq.heappop(pq)\n",
    "            pass_num += 1\n",
    "            for prime in primes:\n",
    "                if val*prime not in hashset:\n",
    "                    heapq.heappush(pq, val*prime)\n",
    "                    hashset.add(val*prime)\n",
    "        return pq[0]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
